package 代码随想录_动态规划.背包_01;

/**
 * @author zx
 * @create 2022-05-29 12:12
 */
public class 求正数数组的最小不可组成和_nowcoder {
    public int getFirstUnFormedNum(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for(int i = 0;i < arr.length;i++){
            min = Math.min(min,arr[i]);
            max += arr[i];
        }
        //dp[j]：数组中最大组成和
        int[] dp = new int[max + 1];
        for(int i = 0;i < arr.length;i++){//遍历物品重量
            for(int j = max;j >= min;j--){//背包容量
                if(j >= arr[i]){//判断某一物品能否放入时直接忽略容量小于该物品质量的情况
                    dp[j] = Math.max(dp[j],dp[j - arr[i]] + arr[i]);
                }
            }
        }
        //最后当承重为i时,放入的重量不为i则认为是最小不可求和
        for(int i = min;i <= max;i++){
            if(dp[i] != i){
                return i;
            }
        }
        return max + 1;
    }
}
